11456. Next greater element

Given an array, print the Next Greater Element for every element.

The Next Greater Element for an element x is the first greater element on the right side of x in the array. Elements for which no greater element exist, consider the next greater element as -1.

Input. The first line contains number n (n ≤ 10⁵). The second line contains n positive integers, each not greater than 10⁹.

Output. For each element of input array print the Next Greater Element.

Sample input	Sample output
10 5 3 8 5 7 4 2 1 3 7	8 8 -1 7 -1 7 3 3 7 -1

SOLUTION

stack

Algorithm analysis

Let’s declare a stack of integers that will store information about the next greater elements. We’ll process the numbers sequentially from right to left. When processing the i-th number:

· remove from the stack the numbers not greater than the i-th number;

· the number at the top of the stack will be the next element greater than the i -th number. If stack is empty, then the next greater element is -1;

· push the i-th number into the stack;

At any moment of time, stack stores numbers in descending order. When the next number arrives, all numbers not greater than it are removed from the stack. After that, the new number takes place at the top of the stack.

Example

Consider the processing of numbers from the example.

Algorithm realization

Read the input data.

scanf("%d", &n);

m.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &m[i]);

Process the numbers sequentially from right to left.

for (i = n - 1; i >= 0; i--)

{

Remove from the stack numbers, no more than m[i].

while (!s.empty() && (s.top() <= m[i])) s.pop();

The next greater element after m[i] will be the number at the top of the stack. If the stack is empty, then push -1 to the resulting array res.

if (s.empty()) res.push_back(-1);

else res.push_back(s.top());

Push number m[i] into stack.

s.push(m[i]);

}

Reverse and print the resulting array.

reverse(res.begin(), res.end());

for (i = 0; i < n; i++)

printf("%d ", res[i]);

printf("\n");